package main.leetcode.clockin.April;

import java.util.Arrays;

/**
 * 542.01矩阵
 *
 * <p>给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
 *
 * <p>两个相邻元素间的距离为 1 。
 *
 * <p>给定矩阵的元素个数不超过 10000。 给定矩阵中至少有一个元素是 0。 矩阵中的元素只在四个方向上相邻: 上、下、左、右。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/01-matrix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day15 {
    public static void main(String[] args) {
        System.out.println(
                Arrays.deepToString(
                        new day15()
                                .updateMatrix(
                                        new int[][] {
                                            {1, 0, 1, 1, 0, 0, 1, 0, 0, 1},
                                            {0, 1, 1, 0, 1, 0, 1, 0, 1, 1},
                                            {0, 0, 1, 0, 1, 0, 0, 1, 0, 0},
                                            {1, 0, 1, 0, 1, 1, 1, 1, 1, 1},
                                            {0, 1, 0, 1, 1, 0, 0, 0, 0, 1},
                                            {0, 0, 1, 0, 1, 1, 1, 0, 1, 0},
                                            {0, 1, 0, 1, 0, 1, 0, 0, 1, 1},
                                            {1, 0, 0, 0, 1, 1, 1, 1, 0, 1},
                                            {1, 1, 1, 1, 1, 1, 1, 0, 1, 0},
                                            {1, 1, 1, 1, 0, 1, 0, 0, 1, 1}
                                        })));
        //        System.out.println(
        //                Arrays.deepToString(
        //                        new day15()
        //                                .updateMatrix(
        //                                        new int[][] {
        //                                            {1, 0, 1, 1, 0, 0, 1, 0, 0, 1},
        //                                            {0, 1, 1, 0, 1, 0, 1, 0, 1, 1},
        //                                            {0, 0, 1, 0, 1, 0, 0, 1, 0, 0},
        //                                            {1, 0, 1, 0, 1, 1, 1, 1, 1, 1},
        //                                            {0, 1, 0, 1, 1, 0, 0, 0, 0, 1},
        //                                            {0, 0, 1, 0, 1, 1, 1, 0, 1, 0},
        //                                            {0, 1, 0, 1, 0, 1, 0, 0, 1, 1},
        //                                            {1, 0, 0, 0, 1, 1, 1, 1, 0, 1},
        //                                            {1, 1, 1, 1, 1, 1, 1, 0, 1, 0},
        //                                            {1, 1, 1, 1, 0, 1, 0, 0, 1, 1}
        //                                        })));
        //        System.out.println(
        //                Arrays.deepToString(
        //                        new day15()
        //                                .updateMatrix(
        //                                        new int[][] {
        //                                            {1, 1, 0, 0, 1, 0, 0, 1, 1, 0},
        //                                            {1, 0, 0, 1, 0, 1, 1, 1, 1, 1},
        //                                            {1, 1, 1, 0, 0, 1, 1, 1, 1, 0},
        //                                            {0, 1, 1, 1, 0, 1, 1, 1, 1, 1},
        //                                            {0, 0, 1, 1, 1, 1, 1, 1, 1, 0},
        //                                            {1, 1, 1, 1, 1, 1, 0, 1, 1, 1},
        //                                            {0, 1, 1, 1, 1, 1, 1, 0, 0, 1},
        //                                            {1, 1, 1, 1, 1, 0, 0, 1, 1, 1},
        //                                            {0, 1, 0, 1, 1, 0, 1, 1, 1, 1},
        //                                            {1, 1, 1, 0, 1, 0, 1, 1, 1, 1}
        //                                        })));
        String s =
                "[[1,0,1,1,0,0,1,0,0,1],[0,1,1,0,1,0,1,0,1,1],[0,0,1,0,1,0,0,1,0,0],[1,0,1,0,1,1,1,1,1,1],[0,1,0,1,1,0,0,0,0,1],[0,0,1,0,1,1,1,0,1,0],[0,1,0,1,0,1,0,0,1,1],[1,0,0,0,1,1,1,1,0,1],[1,1,1,1,1,1,1,0,1,0],[1,1,1,1,0,1,0,0,1,1]]";

        s = s.replace('[', '{');
        s = s.replace(']', '}');
        System.out.println(s);
    }

    // TLE BFS
    //    public int[][] updateMatrix(int[][] matrix) {
    //        int m = matrix.length;
    //        int n = matrix[0].length;
    //        boolean[][] isVisited = new boolean[m][n];
    //        Queue<Integer> queue = new LinkedList<>();
    //        for (int i = 0; i < m; ++i) {
    //            for (int j = 0; j < n; ++j) {
    //                if (matrix[i][j] == 1) {
    //                    matrix[i][j] = -1;
    //                    queue.add(i * m + j);
    //                }
    //            }
    //        }
    //        int i, j, cur;
    //        while (!queue.isEmpty()) {
    //            cur = queue.poll();
    //            i = cur / m;
    //            j = cur % m;
    //            matrix[i][j] = dfs(matrix, isVisited, m, n, i, j, 0);
    //        }
    //        return matrix;
    //    }
    //
    //    private int dfs(int[][] matrix, boolean[][] isVisited, int m, int n, int i, int j, int
    // cur) {
    //        if (i < 0 || i > m - 1 || j < 0 || j > n - 1 || isVisited[i][j]) return
    // Integer.MAX_VALUE;
    //        if (matrix[i][j] == 0) return cur;
    //        if (matrix[i][j] > 0) return matrix[i][j] + cur;
    //        cur += 1;
    //        isVisited[i][j] = true;
    //        int up = dfs(matrix, isVisited, m, n, i - 1, j, cur);
    //        int down = dfs(matrix, isVisited, m, n, i + 1, j, cur);
    //        int left = dfs(matrix, isVisited, m, n, i, j - 1, cur);
    //        int right = dfs(matrix, isVisited, m, n, i, j + 1, cur);
    //        isVisited[i][j] = false;
    //        return Math.min(Math.min(up, down), Math.min(left, right));
    //    }

    //    public int[][] updateMatrix(int[][] matrix) {
    //        int m = matrix.length;
    //        int n = matrix[0].length;
    //        //        Queue<Integer> queue = new LinkedList<>();
    //        Queue<int[]> queue = new LinkedList<>();
    //        for (int i = 0; i < m; ++i) {
    //            for (int j = 0; j < n; ++j) {
    //                if (matrix[i][j] == 1) {
    //                    matrix[i][j] = -1;
    //                } else {
    //                    //                    queue.add(i * m + j);
    //                    queue.add(new int[] {i, j});
    //                }
    //            }
    //        }
    //        int i, j;
    //        int[] cur;
    //        int x, y;
    //        int[][] dir = new int[][] {{1, -1, 0, 0}, {0, 0, -1, 1}};
    //        while (!queue.isEmpty()) {
    //            cur = queue.poll();
    //            //            i = cur / m;
    //            //            j = cur % m;
    //            i = cur[0];
    //            j = cur[1];
    //            for (int k = 0; k < 4; ++k) {
    //                x = i + dir[0][k];
    //                y = j + dir[1][k];
    //                if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] == -1) {
    //                    matrix[x][y] = matrix[i][j] + 1;
    //                    //                    queue.add(x * m + y);
    //                    queue.add(new int[] {x, y});
    //                }
    //            }
    //        }
    //        return matrix;
    //    }

    // dp
    public int[][] updateMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] != 0) {
                    dp[i][j] = m + n;
                }
                if (i > 0) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1); // 上
                }
                if (j > 0) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1); // 左
                }
            }
        }
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (i < m - 1) {
                    dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1); // 下
                }
                if (j < n - 1) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1); // 右
                }
            }
        }
        return dp;
    }
}
